package com.baidu.leetcode.search;

/**
 * @author shilei
 * @create 2021-12-10 14:40
 * 插值查找算法演示-前提要求是数组是有序的
 * 插值查找算法在连续的数组中查找效率很快 数据量大爷一次命中 利用自适应算法
 * 原理介绍：
 * 1、插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
 * 2、将折半查找中的求 mid 索引公式，left 表示左表索引，right表示右边索引
 * 3、int mid = left + (right-left) * (findVal - arr[left]) / (arr[right]-arr[left])
 * 4、比如查找1-99数组中的1的数字下标 按照公式解析
 * 查找1的下标 int mid = 0 + (99-0) * (1-1)/(100-1) = 0 + 99 *0 /99=0  一次命中
 * 查找100的下标 int mid = 0 + (99-0) * (100-1) /(100-1) = 0 + 99 * 99 / 99=99 一次命中
 *
 * 注意事项：
 *  1、对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
 *  2、关键字分布不均匀的情况下，该方法不一定比折半也就是二分查找要好
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        int result = insertValueSearch(arr, 0, arr.length - 1, 80);
        System.out.println(result);
    }

    /**
     * 插值查找算法
     *
     * @param arr 原始数据
     * @return 返回索引
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        System.out.println("查找次数~");
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (midVal > findVal) {
            //向左递归查找
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else if (midVal < findVal) {
            //向右递归查找
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else {
            return mid;
        }
    }
}
